package com.practice.shua1;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * 【leetcode 691. 贴纸拼词】（TODO：从左到右不断尝试）
 * 【题目】：
 * 给定一个字符串str，给定一个字符串类型的数组arr。
 * arr里的每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来。(TODO:每种贴纸可以使用任意张)
 * 返回需要至少多少章贴纸可以完成这个任务。
 * 【例子】:
 * str="babac", arr={"ba", "c", "abcd"}
 * 至少需要两张贴纸“ba”和"abcd"，因为使用这两张贴纸，把每一个字符单独剪剪开，
 * 含有2个'a'、2个'b'、1个'c'。是可以拼出str的。所以返回2。
 *
 * @author lineng
 * @create 2021-05-01 11:06
 */
public class Code_02_StickersToSpellWord {

    // 暴力递归主函数
    public static int myMain(String aim, String[] arr){
        if (aim==null||aim.length()==0){
            return 0;
        }
        if (arr==null || arr.length==0){
            return -1;
        }
        // TODO: 判断aim中的字符种类个数是否 < arr中的字符种类个数
        HashSet<Character> haveCharacters = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            String curString = arr[i];
            char[] chars = curString.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                haveCharacters.add(chars[j]);
            }
        }
        char[] aimChars = aim.toCharArray();
        for (int i = 0; i < aimChars.length; i++) {
            if (!haveCharacters.contains(aimChars[i])){
                return -1;
            }
        }
        return myProcess(aim, arr);
    }

    // 暴力递归
    // 还剩下rest中的字符没有搞定，请继续在arr中选择第一张使用的贴纸，返回最少使用的贴纸数量
    public static int myProcess(String rest, String[] arr) {

        if (rest.equals("")) {
            return 0;
        }

        int next = Integer.MAX_VALUE;
        // 搞定rest的第一张贴纸是啥
        for (String first : arr) {
            char[] firstChars = first.toCharArray();
            HashMap<Character, Integer> firstMap = new HashMap<>();
            for (int i = 0; i < firstChars.length; i++) {
                if (firstMap.containsKey(firstChars[i])) {
                    firstMap.put(firstChars[i], firstMap.get(firstChars[i]) + 1);
                } else {
                    firstMap.put(firstChars[i], 1);
                }
            }
            char[] oldRestChars = rest.toCharArray();
            HashMap<Character, Integer> oldRestMap = new HashMap<>();
            for (int i = 0; i < oldRestChars.length; i++) {
                if (oldRestMap.containsKey(oldRestChars[i])) {
                    oldRestMap.put(oldRestChars[i], oldRestMap.get(oldRestChars[i]) + 1);
                } else {
                    oldRestMap.put(oldRestChars[i], 1);
                }
            }
            // TODO：如果first中一个字符也不在rest中，直接跳过这张贴纸
            int containNumber = 0;

            // old-first
            HashMap<Character, Integer> newRestMap = new HashMap<>();
            Set<Character> oldCharacters = oldRestMap.keySet();
            for (Character ch : oldCharacters) {
                if (firstMap.containsKey(ch) && (firstMap.get(ch) < oldRestMap.get(ch))) {
                    containNumber++;
                    newRestMap.put(ch, oldRestMap.get(ch) - firstMap.get(ch));
                } else if (firstMap.containsKey(ch) && (firstMap.get(ch) >= oldRestMap.get(ch))) {
                    containNumber++;
                    continue;
                } else {
                    newRestMap.put(ch, oldRestMap.get(ch));
                }
            }
            if (containNumber==0){
                continue;
            }
            String newRest = "";
            Set<Character> newRestCharacters = newRestMap.keySet();
            for (Character newCh : newRestCharacters) {
                int count = newRestMap.get(newCh);
                for (int i = 1; i <= count; i++) {
                    newRest += newCh;
                }
            }

            int cur = myProcess(newRest, arr);
            // 当前使用了1张贴纸所以cur+1
            next = Math.min(next, cur+1);
        }

        return next;
    }


    // 傻缓存主函数
    public static int myCacheMain(String aim, String[] arr){
        if (aim==null||aim.length()==0){
            return 0;
        }
        if (arr==null || arr.length==0){
            return -1;
        }
        HashMap<String, Integer> dp = new HashMap<>();

        // TODO（强调）: 判断aim中的字符种类个数是否 <= arr中的字符种类个数，
        //  如果aim中存在arr中不包含的字符直接返回-1
        HashSet<Character> haveCharacters = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            String curString = arr[i];
            char[] chars = curString.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                haveCharacters.add(chars[j]);
            }
        }
        char[] aimChars = aim.toCharArray();
        for (int i = 0; i < aimChars.length; i++) {
            if (!haveCharacters.contains(aimChars[i])){
                return -1;
            }
        }
        return myCacheProcess(aim, arr, dp);
    }



    // 暴力递归提交超时，改用傻缓存，
    // TODO(强调):傻缓存可以AC
    public static int myCacheProcess(String rest, String[] arr, HashMap<String, Integer> dp) {

        if (dp.containsKey(rest)){
            return dp.get(rest);
        }

        if (rest.equals("")) {
            dp.put(rest, 0);
            return dp.get(rest);
        }

        int next = Integer.MAX_VALUE;
        // 搞定rest的第一张贴纸是啥
        for (String first : arr) {
            char[] firstChars = first.toCharArray();
            HashMap<Character, Integer> firstMap = new HashMap<>();
            for (int i = 0; i < firstChars.length; i++) {
                if (firstMap.containsKey(firstChars[i])) {
                    firstMap.put(firstChars[i], firstMap.get(firstChars[i]) + 1);
                } else {
                    firstMap.put(firstChars[i], 1);
                }
            }
            char[] oldRestChars = rest.toCharArray();
            HashMap<Character, Integer> oldRestMap = new HashMap<>();
            for (int i = 0; i < oldRestChars.length; i++) {
                if (oldRestMap.containsKey(oldRestChars[i])) {
                    oldRestMap.put(oldRestChars[i], oldRestMap.get(oldRestChars[i]) + 1);
                } else {
                    oldRestMap.put(oldRestChars[i], 1);
                }
            }
            // TODO（强调）：如果first中一个字符也不在rest中，直接跳过这张贴纸，
            //  containNumber用于记录rest中有几个first中的字符，
            //  下面如果发现containNumber依旧为0，直接跳过当前的贴纸
            int containNumber = 0;

            // old-first
            HashMap<Character, Integer> newRestMap = new HashMap<>();
            Set<Character> oldCharacters = oldRestMap.keySet();
            for (Character ch : oldCharacters) {
                if (firstMap.containsKey(ch) && (firstMap.get(ch) < oldRestMap.get(ch))) {
                    containNumber++;
                    newRestMap.put(ch, oldRestMap.get(ch) - firstMap.get(ch));
                } else if (firstMap.containsKey(ch) && (firstMap.get(ch) >= oldRestMap.get(ch))) {
                    containNumber++;
                    continue;
                } else {
                    newRestMap.put(ch, oldRestMap.get(ch));
                }
            }
            if (containNumber==0){
                continue;
            }
            String newRest = "";
            Set<Character> newRestCharacters = newRestMap.keySet();
            for (Character newCh : newRestCharacters) {
                int count = newRestMap.get(newCh);
                for (int i = 1; i <= count; i++) {
                    newRest += newCh;
                }
            }
            int cur = myCacheProcess(newRest, arr, dp);
            // 当前使用了1张贴纸所以cur+1
            next = Math.min(next, cur+1);
            dp.put(rest, next);
        }

        return dp.get(rest);
    }

}
